package com.xufx.algorithm.sort;

/**
 * 插入排序
 * 1.插入排序的思想是，找出未排序的第一个数字，和其左边的已经排序的数字比较，然后放到合适的位置。
 * 需要注意的一点是，插入排序的里面一层循环方向和外面的一层是相反的
 * 时间复杂度：O(n*n)
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] nums = new int[]{0,1,8,-4,3,3,3,3,-90,7,3,3,6};
        insertSort(nums);
        for (int num: nums) {
            System.out.println(num);
        }
    }

    private static void insertSort(int[] nums){
        for (int i = 1; i < nums.length; i++){
            for(int j = i; j > 0; j--){
                if(nums[j] < nums[j - 1]){
                    int tmp = nums[j];
                    nums[j] = nums[j - 1];
                    nums[j - 1] = tmp;
                }
            }
        }
    }
}
